1. Field of the Invention
The present invention relates to a method for constructing a data structure used for a proximate particle search, whereby a method is obtained for accelerating a proximate particle search by conclusively executing a particle-based simulation using a GPU or other streaming processors, and collision calculation or the like of numerous rigid bodies, for example, can be performed in real time; to a program of the method for constructing a data structure; and to a storage medium for storing the program.
2. Description of the Related Art
A “particle-based simulation” is a simulation method for performing calculations relating to the behavior of each of a large number of particles, in which the object of the simulation is a group (aggregation) of numerous particles. “Spheres” having a constant diameter are usually used as the particles for calculation by computer. When the shape of the object is expressed by an aggregation of spheres, the degree of approximation or the spatial resolution varies depending on the method of determining the size (diameter) of the spheres. Varying the sphere diameter and varying the spatial resolution make it possible to control the calculation accuracy and the calculation speed in the computer simulation calculation.
The abovementioned particle-based simulation has been used in recent years to calculate collisions of numerous rigid bodies, and to calculate the behavior of fluids, particulate bodies, and the like, and to research simulations of collisions, flow, and the like on the screen of a computer display device (Non-patent Document 1 and other publications). The results of this research are described in M. Tanaka et al., “Development of a rigid-body calculation method using a particle method, and application thereof to computer graphics,” Japan Society of Mechanical Engineers, Papers of the 19th Computational Mechanics Conference, pp. 701-702, 2006. Research of these simulation techniques is important for the technology that forms the foundation of computer graphics (CG).
In the particle-based simulation research described above, numerous methods have been used in the past for utilizing a CPU to create a calculation algorithm. However, little research has been done concerning particle based simulations in which a GPU (Graphics Processing Unit) or a streaming processor is actively utilized. In such past research using a GPU, a proximate particle search was executed by a CPU, and the search data obtained by the CPU was transferred to the GPU for image processing. According to this technique, the CPU is used as the primary calculation execution unit, the calculation algorithm of the proximate particle search is executed by the CPU, and the GPU as an auxiliary calculation execution unit executes only a calculation algorithm for image display processing. Consequently, the conventional calculation technique was not configured so that the calculation algorithms of the proximate particle search and the image processing in the particle-based simulation are concluded and executed only within the GPU.
Since a configuration in which all calculation (image processing, construction of the data structure used in the proximate particle search, and the like) is concluded only by the GPU is not adopted in the conventional particle-based simulation calculation, the computational efficiency is unsatisfactory, the inherent image processing capability of the GPU cannot be adequately demonstrated, and it is impossible to perform collision calculation of numerous rigid bodies and other real-time rigid body simulations, fluid simulations, and the like. There is therefore a need to develop a method for conclusively utilizing a GPU or other steaming processor to execute construction of a data structure used in a proximate particle search by the GPU or the like, and demonstrating the maximum image processing capability of the GPU.